﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Sol76
{



    public string MinWindow2(string s, string t)
    {

        string res = "";

        for (int start = 0; start < s.Length; start++)
        {
            {
                //遍历所有长度为i,起点为start的子串
                for (int end = start; end < s.Length; end++)
                {

                    Dictionary<char, int> dict = new Dictionary<char, int>();
                    for (int i = 0; i < t.Length; i++)
                    {
                        if (dict.TryGetValue(t[i], out int nums))
                        {//存过这个字符，就加1
                         //dict[t[i]] = nums++;
                            nums++;
                        }
                        else
                        {
                            dict[t[i]] = 1;
                        }


                    }
                    bool have = StrCompare(dict, s, start, end);
                    if (have)
                    {
                        res = s.Substring(start, end);
                    }
                }


            }

        }
        return res;




    }



    private bool StrCompare(Dictionary<char, int> dict, string s, int start, int end)
    {
  
        for (int i = start; i <= end; i++)
        {
            //判断t是不是s的子集,也就是s包含t的map吗

            if (dict.ContainsKey(s[i]))//包含这个数，就把次数减掉，保证次数最后小于等于0
            {
                dict[s[i]]--;//不要随便修改字典的值
            }
            foreach (int num in dict.Values)
            {
                if (num > 0)//说明窗口里面的数少
                {
                    return false;
                }
            }



        }
        return true;
    }

    public string MinWindow(string s, string t)
    {
        Dictionary<char, int> dict = new Dictionary<char, int>();//
        Dictionary<char, int> cntS = new Dictionary<char, int>();
        for (int i = 0; i < t.Length; i++)
        {
            if (dict.TryGetValue(t[i], out int nums))
            {//存过这个字符，就加1
                dict[t[i]] = nums+1;
                //nums++;
            }
            else
            {
                dict[t[i]] = 1;
            }


        }
        //foreach(var v in dict)
        //{
        //    Console.Write(v.Key + " ");
        //    Console.Write(v.Value + " ");
        //}

        int Lens = s.Length;
        int resL = -1;//最后结果的左右子串
        int resR=Lens;
        int left= 0;
        //Console.WriteLine(" cntS");
        for (int right=0; right< Lens; right++) {

            if (cntS.TryGetValue(s[right], out int nums))
            {//存过这个字符，就加1
                cntS[s[right]] = nums+1;
                //nums++;
            }
            else
            {
                cntS[s[right]] = 1;
            }

            //foreach (var v in cntS)
            //{
            //    Console.Write(v.Key+" ");
            //    Console.Write(v.Value + " ");
            //}

            //判断
            //bool cover = isCovered(dict, cntS);
            //Console.WriteLine(isCovered(dict, cntS) + " ");
            while (isCovered(dict, cntS))
            {
               
                //更新最小
                if ((right-left) < (resR-resL)) {

                    resL = left;
                    resR = right;
                }
                //Console.WriteLine(left);
                //Console.WriteLine(s[left]);

                //cntS.Remove(s[left++]);//左边收缩,次数减1就行
                cntS[s[left]]= cntS[s[left]] - 1;//左边收缩,次数减1就行
                left++;
                //cover = isCovered(dict, cntS);
            }


        }

        String res = "";
        if(resL < 0) {
            return res;
        }
        else
        {
         
            res =s.Substring( resL,resR-resL+1);
            return res;
        }






    }

    private bool isCovered(Dictionary<char, int> dict, Dictionary<char, int> cntS)
    {
        //检测是否包含
        foreach(var  keyValue in dict)
        {

            if (cntS.TryGetValue(keyValue.Key,out int num))
            {
                if (num < keyValue.Value)//说明不涵盖
                {
                    return false;
                }
            }
            else
            {
                return false;
            }
        }

        return true;

    }
}
    class Program176
{
    static void Main176(string[] args)
    {
        Sol76 sol = new Sol76();
        //string s = "ADOBECODEBANC";
        //string t = "ABC";
        string s = "a";
        string t = "aa";
        string res = sol.MinWindow(s, t);
        Console.WriteLine(res);
        Console.ReadKey();

    }
}

